沉下心来分析HashMap的源码（三）学习红黑树
HashMap的源码在JDK 1.8后引入了红黑树，但是看到红黑树的定义：
- 每个节点或者是红色，或者是黑色
- 根节点是黑色
- 每一个叶子节点(最后的空节点)是黑色的
- 如果一个节点是红色的，那么它的孩子节点都是黑色的
- 从任意一个节点到叶子节点，经过的黑色节点是一样的
完全的不清楚为什么这么定义，以及这么定义的原因是什么。
先导
先说红黑树的由来，是为了查找的平衡，从二叉查找树说起。
二叉查找树：从根节点开始，左节点的值小于根节点，右节点的值大于右节点。并且每一颗子树都满足这个条件，所以便于查找：查找的时候，只需要比对就能够瞬速的找到所在子树，继而找到对应的节点。但是二叉查找树有一个缺点就是：容易偏向一侧，我们向往的二叉查找树是图一，结果却有很多图二的情况。
平衡树：2-3树
在这种需求下，平衡树的概念就应运而生了。红黑树就是一种平衡树，它可以保证二叉树基本符合我们预料的那种平衡的结构，但是理解红黑树之前，必须先了解另一种树，叫2-3树，红黑树背后的逻辑就是它。
2-3树：2-3树满足二分搜索树的性质。不同的是在2-3树中，存在两种节点。一种是有两个叶子节点的，我们称作“2节点” 如图3；另一种是有三个叶子节点的，我们称作“3节点”，如图4，图5展示的是一个完整的2-3 树，满足从根节点到任意一个叶子节点的高度都是相同的。
2-3树如何保持平衡
2-3树平衡的保持，主要依赖两个操作：拆分和合并。其中拆分主要发生在3节点插入时候，如下图6，图7完整的展示可一个查分的过程：
拆分的过程主要是形成了一个4节点（类似于2节点，3节点的概念），(4 7 9) 这个节点，然后通过4节点的中间状态查分为三个2节点.
但是在图7的第二步，拆分过后的2-3树已经不满足：从根节点到任意的叶子节点的高度是完全一致的平衡性，所以我们需要合并的操作，如图7中的第三步。
如果合并过程中，出现了四节点，那么我们再次的查分，这两个操作可以混合使用，如图8.
2-3树和红黑树的关系
对于2-3树中的“2节点”，对应于红黑树中的“黑节点”，即相当于普通二分搜索树中的一个节点。
对于2-3树中的“3节点”，相当于普通二分搜索树中的两个节点融合在一起，我们如何来描述这种融合在一起的两个节点之间的关系呢？
其实很简单，如果我们将连接这两个节点的边涂成红色，就可以表示这两个节点是融合的关系，即2-3树中的一个“3节点”。
对于树这种数据结构，我们在定义的时候通常都是针对节点进行定义，并没有对节点之间的边进行定义，我们如何来表示这条被涂成红色的边呢？
大家都知道，对于树中的任意一个节点，都是只有一个父亲节点，所以与其父节点相连接的边可以用该节点进行表示。那么我们就可以将这两个节点中较小的节点（作为左子树的节点）涂成红色，就可以很好地表示这两个节点融合的关系了。
如下图所示：
然后一颗2-3树的就可以转化为一颗红黑树了，如下图所示：
再次的分析红黑树的性质
讨论了2-3树与红黑树之间的关系，我们再回过头来看一下红黑树的5条定义和性质，会发现很好理解了。
1.每个节点或者是红色，或者是黑色 这条定义很好理解，在此不做解释。
2.根节点是黑色
根据之前说过的，红色的节点对应于2-3树中“3节点”中较小的那个节点，拆成两个“2节点”的话则是一个左子树的节点，即红色的节点总是可以和其父节点进行融合，所以红色节点一定有父节点，显然根节点不能是红色，所以根节点是黑色。
3.每一个叶子节点(最后的空节点)是黑色的
这条性质和第2条是对应的。对于叶子节点（最后的空节点），一颗空树的根节点也为黑色，所以与其说第三条是一条性质，不如说也是一个定义。
4.如果一个节点是红色的，那么它的孩子节点都是黑色的
根据上面2-3树与红黑树两种节点的对比图，我们很容易看到，红色节点的两个子树，对应2-3树中的话，要么是一个“2节点”，要么是一个“3节点”，而不管是“2节点”还是“3节点”，相连的第一个节点都是黑色的，所以说红色节点的孩子节点都是黑色的。
5.从任意一个节点到叶子节点，经过的黑色节点是一样的
根据2-3树与红黑树的关系对比图，可以发现，红黑树中一个黑色节点对应2-3树中一整个节点（“2节点”或“3节点”），而2-3树是完全平衡的树，从根节点到任意路径的叶子节点，经过的节点个数都是相同的，对应红黑树中，即从任意节点到叶子节点，经过的黑色节点是一样的。
对比2-3树总结起来，其实也就两条。其中一条是关于着色的：每个节点都有颜色，非红即黑。根节点，叶子节点为黑色。红色节点的孩子节点为黑色。另外一条是关于2-3树的平衡性的。即是到每一个叶子节点是平衡的，对应的红黑树，也就是经过的黑色节点是一样的。